import java.util.*;
public class mergeTwoLists {
    /**
     * 合并两个有序链表
     */
    public class ListNode{
        int val;
        ListNode next;
        ListNode(){}
        ListNode(int val){
            this.val=val;
        }
        ListNode(int val,ListNode next){
            this.val=val;
            this.next=next;
        }
    }

    public ListNode method(ListNode list1,ListNode list2){
        ListNode dummy=new ListNode(0);
        ListNode cur=dummy;
        while(list1!=null && list2!=null){
            if(list1.val< list2.val){
                cur.next=list1;
                list1=list1.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if(list1!=null){
            cur.next=list1;
        }else{
            cur.next=list2;
        }

        return dummy.next;
    }
    public static void main(String[] args) {
        mergeTwoLists m=new mergeTwoLists();

        ListNode test1=m.new ListNode(1);
        test1.next = m.new ListNode(2);
        test1.next.next = m.new ListNode(3);
        test1.next.next.next = m.new ListNode(4);


        ListNode test2=m.new ListNode(2);
        test2.next = m.new ListNode(3);
        test2.next = m.new ListNode(4);
        test2.next = m.new ListNode(5);

        ListNode res = m.method(test1,test2);

        // 输出方式1：
//        while(res!=null) {
//            System.out.print(res.val + " ");
//            res = res.next;
//        }
        // 输出合并后的含有括号标准形式
        // 输出方式2：
        StringBuilder sb=new StringBuilder();
        sb.append("[");
        while(res!=null){
            sb.append(res.val);
            if(res.next!=null){
                sb.append(", ");
            }
            res =res.next;
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}
